package com.briup.day25;

import com.briup.day21.Looper;

import com.briup.day21.MyCollectionImpl2.Node;

public class MyLinkedList implements MyList {
	//只需保存一个头节点便可间接访问整个链表结构
	private Node first;
			
	private int size;

	//节点内部类
	public static class Node {
		public Object data; //要保存的数据
		public Node next;   //指向下一个地址的引用
		public Node(Object o) {
			data = o;
		}
	}
	
	@Override
	public boolean add(Object o) {
		
		Node node = new Node(o);
		
		//第一次向链表中插入数据
		if (first == null) {
			first = node;
		}
		else { //需要找到当前链表的尾节点
				//创建一个新的Node保存o，让尾节点指向它，让它充当新的尾节点
			Node n = first;
			while (n.next != null) {
				n = n.next;
			}
			//循环结束，n就是尾节点
			n.next = node;
		}
		size++;
		return true;
	}

	@Override
	public void clear() {
		//遍历链表，释放每两个节点之间的关联关系
		Node n = first;
		while (n != null) {
			Node next = n.next;
			n.next = null;
			n.data = null;
			n = next;
		}
		//重置头节点
		first = null;
	}

	@Override
	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		Node n = first;
		if(o == null) {
			while (n != null) {
				if (n.data == null) 
					return true;
				n = n.next;
			
			}
		}else {
			while (n != null) {
				if(o.equals(n.data))
					return true;
				n = n.next;
			}
		}
		//重置头节点
		//first = null;
		return false;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return first == null;
	}

	@Override
	public boolean remove(Object o) {
		//链表非空
		if (first == null) {
			return false;
		}
		
		//通过遍历找到要删除的元素存在哪个节点
		if (o == null) {
			Node n = first;		//当前节点
			Node b = null;   //上一个节点
			
			if (o == n.data) {
				removeFirst();
				return true;
			}
			
			while (n != null) {
				if (n.data == null) {
					//下一节点n.next
					unlink(b, n);
					return true;
				}
				b = n;
				n = n.next;
			}	
		}else {
			Node n = first;
			Node b = null;
			//是否头节点
			if (o.equals(n.data)) {
				removeFirst();
				return true;
			}
			while (n != null) {
				if(o.equals(n.data)) {
					unlink(b, n);
					return true;
				}
				b = n;
				n = n.next;
			}
			
		}
		return false;
	}
	
	//删除非头节点
	private void unlink(Node before, Node curr) {
		// 先临时保存下一个节点的地址
		Node next = curr.next;
		// 把被删节点的data和next属性都清空
		curr.data = null;
		curr.next = null;
		// 把上一个节点指向下一个节点
		before.next = next;
		size--;
	}
	
	//删除头节点
	private void removeFirst() {
		//二节点
		Node second = first.next;
		//释放头节点
		first.data = null;
		first.next = null;
		//二节点充当头节点
		first = second;
		size--;
		
	}

	@Override
	public int size() {
		/*int count = 0;
		Node n =first;
		while (n != null) {
			count++;
			n = n.next;
		}*/
		return size;
	}

	
	@Override
	public Object[] toArray() {
		//创建一个数组
		Object[] arr = new Object[size];
		Node node = first;
		//遍历
		for (int i = 0; i < arr.length; i++) {
			arr[i] = node.data;
			node = node .next ;
		}
		return arr;
	}
	
	@Override
	public MyIt iterator() {
		// TODO Auto-generated method stub
		return new MyIt();
	}
	
	private  class MyIt implements MyIterator {
		private Node curr = first;

		@Override
		public boolean hasNext() {

			return curr != null;
		}

		@Override
		public Object next() {
			Object data = curr.data;
			curr = curr.next;
			return data;
		}
		
	}
	//临时打印
	public void print() {
		Node n = first;
		while (n != null) {
			System.out.println(n.data);
			n = n.next;
		}
	}

/******************************************************************************************/
	
	// 把o添加到链表中第index个位置上
	@Override
	public void add(int index, Object o) {
		if (index < 0 || index > size) {
			System.out.println("传入的索引值不合法，插入失败！");
			return ;
		}
		// 创建一个新的节点
		Node node = new Node(o);
		
		// 对于插入头节点进行特殊处理
		if (index == 0) {
			// 直接让新节点指向头节点
			node.next = first;
			// 让新节点充当新的头节点
			first = node;
			size++;
			return;
		}
		
		// 找index - 1位置上的节点
		Node b = first;
		for (int i = 0; i < index - 1; i++) 
			b = b.next;
		
		// 临时保存b当前的下一个节点
		Node next = b.next;
		// 让前一个节点指向新节点
		b.next = node;
		// node指向原来b.next
		node.next = next;
		size++;
		
	}
	
	// 删除链表中index位置上的元素，返回值就是被删掉的元素
	@Override
	public Object remove(int index) {
		if (index < 0 || index >= size) {
			System.out.println("传入的索引值不合法，删除失败！");
			return null;
		}
		// 删除头节点特殊处理
		if (index == 0) {
			Node second = first.next;
			Object obj = first.data;
			first.data = null;
			first.next = null;
			// 让原来的第二个节点充当新的头节点
			first = second;
			size--;
			return obj;
		}
		
		// 需要让index - 1节点的next直接指向index + 1
		Node b = first;
		for (int i = 0; i < index - 1; i++) 
			b = b.next;
		
		// b=before 被删除的前一个节点
		// c=current 被删除的节点
		// n=next 被删除的下一个节点
		Node c = b.next;
		Node n = c.next;
		
		// 先把被删节点中的元素取出，用于方法的返回
		Object obj = c.data;
		// 断开被删节点和它指向的后一个节点的关联
		// 并清空它保存的元素
		c.next = null;
		c.data = null;
		// 让前一个节点指向后一个节点
		b.next = n;
		
		size--;
		return obj;
	}

	@Override
	public Object set(int index, Object o) {
		Node node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		//保存被替换元素引用
		Object object = node.data;
		//index位置上的元素替换为o
		node.data = o;
		//返回的是被替换的元素
		return object;
	}

	@Override
	public Object get(int index) {
		Node node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node.data;
	}

}
